package com.arceus.leetcode.dytedance;

/**
 * @author : iron
 * @version : 1.0.0
 * @date : 5:59 PM 2019/1/4
 */

public class T9 {

    public static void main(String[] args) {
        int[][] grid = new int[][]{{0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0},
                {0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0},
                {0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0},
                {0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0},
                {0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0},
                {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0},
                {0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0},
                {0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0}};
        int res = maxAreaOfIsland(grid);
    }

    public static int maxAreaOfIsland(int[][] grid) {
        /**
         深度优先遍历, 到达边界外或访问到为0的位置则返回0,否则
         先把该位置的1置为0(作为访问过的标记相当于visited数组)
         随后递归的访问四个方向, 并把返回值累加作为与该节点连通的
         最大岛屿面积
         **/
        if (grid.length < 1) return 0;
        int maxA = 0;
        for (int i = 0; i < grid.length; ++i) {
            for (int j = 0; j < grid[0].length; ++j) {
                if (grid[i][j] == 1)
                    maxA = Math.max(maxA, dfs(grid, i, j));
            }
        }
        return maxA;
    }

    private static int dfs(int[][] grid, int x, int y) {
        if (x < 0 || x >= grid.length || y < 0 || y >= grid[0].length || grid[x][y] == 0)
            return 0;
        grid[x][y] = 0;
        return 1 + dfs(grid, x + 1, y) + dfs(grid, x - 1, y) +
                dfs(grid, x, y + 1) + dfs(grid, x, y - 1);
    }
}
